|
|
Hluboké zásobníkové automaty konečného indexu
Poncová, Vendula ; Horáček, Petr (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce představuje několik modifikací hlubokých zásobníkových automatů s ohledem na redukci počtu stavů nebo nevstupních symbolů. Je ukázáno, že síla hlubokých zásobníkových automatů konečného indexu není ovlivněna omezením nevstupních symbolů na jeden, tudíž tyto automaty charakterizují nekonečnou hierarchii jazykových rodin vycházejících z programových gramatik konečného indexu. Na základě principu tohoto automatu je stanovena normální forma hlubokých zásobníkových automatů. Nakonec zavádím zobecněný hluboký zásobníkový automat, který expanduje nejvrchnější možný nevstupní symbol na zásobníku. Tento automat spolu s jeho zredukovanými formami je ekvivalentní se stavovými gramatikami.
|
|
|
Sekvenční a paralelní gramatiky: vlastnosti a aplikace
Klobučníková, Dominika ; Martiško, Jakub (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto práca sa zaoberá problematikou sekvenčných a paralelných gramatík. Obe skupiny zastrešujú veľké množstvo gramatických tried, väčšina ktorých však nemá veľké uplatnenie kvôli komplikáciám spojeným s ich spracovaním. Práca skúma niektoré takéto gramatiky, ako napríklad gramatiky s rozptýleným kontextom, multigeneratívne gramatické systémy a interaktívne L-systémy s dôrazom na ich normálne formy. Práca následne predstavuje niekoľko algoritmov využívajúcich vlastnosti týchto gramatík, ako aj ich normálnych foriem. Tieto algoritmy sú založené na algoritme Cocke-Younger-Kasami pre bezkontextové gramatiky a dokážu spracovať ľubovoľnú gramatiku v príslušnej normálnej forme. Posledná časť práce predstavuje program implementujúci navrhnuté algoritmy.
|
|
|
Knihovna pro boolovské funkce v algebraické normální formě
Vasilišin, Maroš ; Mrázek, Vojtěch (oponent) ; Dobai, Roland (vedoucí práce)
Táto bakalárska práca sa zaoberá návrhom a implementáciou knižnice v jazyku C pre manipuláciu Boolovych funkcií v Algebraickej Normálnej Forme. Väčšina existujúcich reprezentácií Boolovych funkcií je založená na binárnych rozhodovacích diagramoch. Algebraická Normálna Forma poskytuje oproti binárnym rozhodovacím diagramom určité výhody, napríklad tú, že sa dá z nej v lineárnom čase určiť Boolova hodnota funkcie. Implementovaná knižnica za pomoci jednoduchých štruktúr poskytuje efektívnu reprezentáciu Boolovej funkcie v programe. Výskumom sme zistili, že reprezentácia pomocou Algebraickej Normálnej Formy má svoj využitie, a v určitých prípadoch dosahuje lepšie výsledky ako reprezentácia pomocou binárnych rozhodovacích diagramov.
|
|
|
Sekvenční a paralelní gramatiky: vlastnosti a aplikace
Klobučníková, Dominika ; Martiško, Jakub (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto práca sa zaoberá problematikou sekvenčných a paralelných gramatík. Obe skupiny zastrešujú veľké množstvo gramatických tried, väčšina ktorých však nemá veľké uplatnenie kvôli komplikáciám spojeným s ich spracovaním. Práca skúma niektoré takéto gramatiky, ako napríklad gramatiky s rozptýleným kontextom, multigeneratívne gramatické systémy a interaktívne L-systémy s dôrazom na ich normálne formy. Práca následne predstavuje niekoľko algoritmov využívajúcich vlastnosti týchto gramatík, ako aj ich normálnych foriem. Tieto algoritmy sú založené na algoritme Cocke-Younger-Kasami pre bezkontextové gramatiky a dokážu spracovať ľubovoľnú gramatiku v príslušnej normálnej forme. Posledná časť práce predstavuje program implementujúci navrhnuté algoritmy.
|
|
|
Knihovna pro boolovské funkce v algebraické normální formě
Vasilišin, Maroš ; Mrázek, Vojtěch (oponent) ; Dobai, Roland (vedoucí práce)
Táto bakalárska práca sa zaoberá návrhom a implementáciou knižnice v jazyku C pre manipuláciu Boolovych funkcií v Algebraickej Normálnej Forme. Väčšina existujúcich reprezentácií Boolovych funkcií je založená na binárnych rozhodovacích diagramoch. Algebraická Normálna Forma poskytuje oproti binárnym rozhodovacím diagramom určité výhody, napríklad tú, že sa dá z nej v lineárnom čase určiť Boolova hodnota funkcie. Implementovaná knižnica za pomoci jednoduchých štruktúr poskytuje efektívnu reprezentáciu Boolovej funkcie v programe. Výskumom sme zistili, že reprezentácia pomocou Algebraickej Normálnej Formy má svoj využitie, a v určitých prípadoch dosahuje lepšie výsledky ako reprezentácia pomocou binárnych rozhodovacích diagramov.
|
|
|
Hluboké zásobníkové automaty konečného indexu
Poncová, Vendula ; Horáček, Petr (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce představuje několik modifikací hlubokých zásobníkových automatů s ohledem na redukci počtu stavů nebo nevstupních symbolů. Je ukázáno, že síla hlubokých zásobníkových automatů konečného indexu není ovlivněna omezením nevstupních symbolů na jeden, tudíž tyto automaty charakterizují nekonečnou hierarchii jazykových rodin vycházejících z programových gramatik konečného indexu. Na základě principu tohoto automatu je stanovena normální forma hlubokých zásobníkových automatů. Nakonec zavádím zobecněný hluboký zásobníkový automat, který expanduje nejvrchnější možný nevstupní symbol na zásobníku. Tento automat spolu s jeho zredukovanými formami je ekvivalentní se stavovými gramatikami.
|
host ::
RSS.